package com.test.maze;


import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Main {
    private static String[][] maze;
    private static boolean hasG = false;
    private static int rowNumber = 0;
    private static int columnNumber = 0;
    private static final String  RANGE = "123456789G";
    private static final String[] ACTIONS = new String[]{"L","R","U","D"}; //left/right/up/down
    private static List<Data> visited = new ArrayList<>();
    private static List<String> solution = new ArrayList<>();
    private static Queue<Data> queue = new LinkedList<>();


    public static void main(String[] args) throws Exception {
        readData();
        outputMaze();
        evaluation();
    }


    private static void readData(){
        ///Users/tshe/Documents/file.txt
        System.out.println("Please input the maze file(.txt) full path.");
        Scanner sc = new Scanner(System.in);
        String path = sc.nextLine();

        File file = new File(path);

        while(!path.contains(".txt")){
            System.out.println("File is wrong.Please input txt file's path");
            path = sc.nextLine();
            file = new File(path);
        }

        while (!file.exists()){
            System.out.println("File path is wrong.Please input again.");
            path = sc.nextLine();
            file = new File(path);
        }

        FileReader reader = null;
        BufferedReader br = null;

        try {
            reader = new FileReader(file);
            br = new BufferedReader(reader);

            String str;
            StringBuffer sb = new StringBuffer();
            int index = 0;

            while((str = br.readLine()) != null) {
                index ++;

                if(index == 1){
                    rowNumber = Integer.valueOf(str);
                    continue;
                }

                if(index == 2){
                    columnNumber = Integer.valueOf(str);
                    maze = new String[rowNumber][columnNumber];
                    continue;
                }

                if(index > (rowNumber + 2)){
                    System.out.println("Wrong data,please check.");
                    return;
                }

                convertDataToMaze(str, index - 3, columnNumber);
            }

            if(!hasG){
                System.out.println("Wrong data,please check.");
            }



        }catch (Exception e){
            System.out.println("Wrong data,please check.");

        }finally {

            if(null != br){
                try {
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            if(null != reader){
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }

            }
        }


    }

    private static void evaluation(){
        Data root = new Data(0, 0, "Root", null);
        queue.offer(root);

        boolean isSolved = false;

        while (!queue.isEmpty() && !isSolved){
            Data current = queue.poll();

            if(!isVisited(current)){
                String value = maze[current.getX()][current.getY()];

                visited.add(current);

                if(value.equals("G")){
                    isSolved = true;
                    int depth = 0;
                    Data last = visited.get(visited.size() - 1);

                    while(!last.equals(root)){
                        solution.add(last.getAction());
                        last = last.getParent();
                        depth += 1;
                    }

                    Collections.reverse(solution);

                    System.out.println("Solution is：");
                    for (String s : solution) {
                        System.out.print(s + " ");
                    }
                    System.out.println("");

                }else{
                    int valueNum = Integer.valueOf(value);
                    int xNum = Integer.valueOf(current.getX());
                    int yNum = Integer.valueOf(current.getY());
                    int maxColIndex = columnNumber - 1;
                    int maxRowIndex = rowNumber - 1;

                    for (String action : ACTIONS) {
                        if(action.equals("U")){
                            if(xNum - valueNum >= 0 && xNum - valueNum <= maxColIndex){
                                Data data = new Data(xNum - valueNum, yNum, action, current);

                                if(!isVisited(data)){
                                    queue.offer(data);
                                }

                            }


                        }else if(action.equals("D")){
                            if(xNum + valueNum >= 0 && xNum + valueNum <= maxColIndex){
                                Data data = new Data(xNum + valueNum, yNum, action, current);

                                if(!isVisited(data)){
                                    queue.offer(data);
                                }

                            }

                        }else if(action.equals("L")){
                            if(yNum - valueNum >= 0 && yNum - valueNum <= maxRowIndex){
                                Data data = new Data(xNum, yNum - valueNum, action, current);

                                if(!isVisited(data)){
                                    queue.offer(data);
                                }

                            }

                        }else{//R
                            if(yNum + valueNum >= 0 && yNum + valueNum <= maxRowIndex){
                                Data data = new Data(xNum, yNum + valueNum, action, current);

                                if(!isVisited(data)){
                                    queue.offer(data);
                                }

                            }

                        }
                    }

                }
            }

            if(queue.size() > 1000 || visited.size() > 300){
                System.out.println("no Solution");
            }


        }

        if(!isSolved){
            System.out.println("No Solution");
        }
    }



    private static boolean convertDataToMaze(String data, int row, int columnNumber){
        if(null == maze || null == data){
            System.out.println("File's content is wrong.");
            return false;
        }


        if(data.contains("G")){
            hasG = true;
        }

        int length = data.length();

        if(length != columnNumber){
            System.out.println("column is wrong.");
            return false;
        }

        for(int i = 0; i < length; i++){
            String element = data.substring(i, i + 1);

            if(!RANGE.contains(element)){
                System.out.println("File's content is wrong.");
                return false;
            }

            maze[row][i] = element;
        }

        return true;

    }


    private static void outputMaze(){
        System.out.println("The maze is:\n");

        for(int i = 0; i < rowNumber; i++){
            for(int j = 0; j < columnNumber; j++){
                System.out.print(maze[i][j] + "  ");
            }

            System.out.println();
        }
    }


    private static boolean isVisited(Data data){
        for (Data row : visited) {
            if(row.equals(data)){
                return true;
            }
        }

        return false;
    }



}
